- SL
- SL (pronunc. [ése éle]) Sigla de «sociedad limitada».
* * *
En teoría de la complejidad computacional, la clase de complejidad SL (espacio logarítmico simétrico) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, tal que: 1. Si la respuesta es positiva, existe uno o más cómputos de la máquina que aceptan. 2. Si la respuesta es negativa, todos los cómputos de la máquina rechazan la entrada. 3. Si la máquina puede hacer una transición no determinista entre una configuración A y una configuración B, también puede hacer una transición de B hacia A (condición de simetría).
Enciclopedia Universal. 2012.
